package leetcode;

/**
 * Created by Ghost on 2014/12/28 0028.
 */
public class Palindrome_Partitioning_II {
    private boolean judge(int i, int j, char[] strs, boolean[][] p) {
        if (strs[j] == strs[i] && (j - i < 2 || p[i + 1][j - 1]))
            p[i][j] = true;
        else
            p[i][j] = false;
        return p[i][j];
    }

    public int minCut(String s) {
        if (s.length() == 0)
            return 0;
        char[] strs = s.toCharArray();

        int[] w = new int[strs.length];//for the times to seprate
        boolean[][] p = new boolean[strs.length][strs.length];//for the palindrome judge.
        for (int i = 0; i < w.length; i++) {
            p[i][i] = true;
            w[i] = i;
        }

        for (int i = 1; i < w.length; i++) {
            if (judge(0, i, strs, p)) {
                p[0][i] = true;
                w[i] = 0;
            } else
                for (int j = 0; j < i; j++) {
                    if (judge(j + 1, i, strs, p)) {
                        w[i] = Math.min(w[i], 1 + w[j]);
                    }
                }
        }

        return w[w.length - 1];

    }

    public static void main(String[] args) {
        Palindrome_Partitioning_II palindrome_partitioning_ii = new Palindrome_Partitioning_II();
        System.out.println(palindrome_partitioning_ii.minCut("a"));
    }
}
